\input{euler.tex}

\begin{document}

\problem[29]{Distinct Terms of the Form $a^b$}

Consider all integer combinations of $a^b$ for $2 \le a \le 5$ and $2 \le b \le 5$:
\begin{center}
\begin{tabular}{c c c c c}
$2^2=4$ & $2^3=8$ & $2^4=16$ & $2^5=32$ \\
$3^2=9$ & $3^3=27$ & $3^4=81$ & $3^5=243$ \\
$4^2=16$ & $4^3=64$ & $4^4=256$ & $4^5=1024$ \\
$5^2=25$ & $5^3=125$ & $5^4=625$ & $5^5=3125$ \\
\end{tabular}
\end{center}

If they are then placed in numerical order, with any repeats removed, we get the following sequence of 15 distinct terms:

4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125.

How many distinct terms are there in the sequence generated by $a^b$ for $2 \le a \le 100$ and $2 \le b \le 100$?

\solution

The key is to enumerate duplicate terms $a^b = c^d$, where $a \ne c$ and $2 \le a, b, c, d \le M = 100$. It is easy to see that in order for this to hold, $a$ and $c$ must have the same prime factors (though not necessary to the same power). Factorizing $a$ and $c$ as
\begin{equation}
a = p_1^{k_1} \cdots p_r^{k_r} , c = p_1^{l_1} \cdots p_r^{l_r} , \label{eq:29.1}
\end{equation}
and we require that
\begin{equation}
k_1 b = l_1 d, \cdots, k_r b = l_r d . \label{eq:29.2}
\end{equation}

% which can be rearranged as
% \begin{equation}
% \frac{d}{b} = \frac{k_i}{l_i} = \frac{k_i / g}{l_i / g}, \label{eq:29.1}
% \end{equation}
% where $g = \gcd(b, d)$. 

Next, define the \emph{root} of a positive number $a$ to be the smallest positive integer whose integral power is $a$, and denote it by $a_0$. It's easy to find 
\begin{equation}
a_0 = p_1^{k_1/g} \cdots p_r^{k_r/g}, \label{eq:29.3}
\end{equation}
where $g = \gcd(k_1, \ldots, k_r)$. Combining \eqref{eq:29.2} and \eqref{eq:29.3} shows that if $a^b = c^d$, then $a$ and $c$ must have the same root. In other words, powers of different root cannot be equal.

Therefore, we can partition powers of the form $a^b$ by their root, $a_0$. Each family is represented by a different $a_0$. Since powers of different roots cannot be equal, we can count the distinct powers family by family, and then sum them up. For powers in the same family with root $a_0$, we have
\[
a^b = (a_0^x)^y = a_0^{xy},
\]
where
\[
1 \le x \le \lfloor \log_{a_0} M \rfloor, 2 \le y \le M .
\]
Thus, we just need to count the number of unique products $xy$ subject to the above range. 

Formally, let $D(x_1, x_2, y_1, y_2)$ denote the number of unique products of $(x, y)$ for $x_1 \le x \le x_2$ and $y_1 \le y \le y_2$. Then the answer to this problem is
\begin{equation}
\sum D(1, \lfloor \log_a M \rfloor, 2, M) , \label{eq:29.5}
\end{equation}
where $2 \le a \le M$ and $a$ is not a perfect power.

To compute $D(x_1, x_2, y_1, y_2)$, we generate all possible products, sort them, and count the unique terms. This certainly could be improved.

Finally, note that $\lfloor \log_a M \rfloor$ is constant for a range of $a$. Therefore we can improve formula \eqref{eq:29.5} a bit by rewriting it as
\begin{equation}
\sum_{L=1}^{\lfloor \log_2 M \rfloor} D(1, L, 2, M) \, \# \big\{ a \,\big|\, \lfloor \log_{a} M \rfloor = L \big\} . \label{eq:29.6}
\end{equation}
where $2 \le a \le M$ and $a$ is not a perfect power.

\complexity

We use a sieving method to find all perfect powers, which takes $\BigO(M \ln M)$ time and $\BigO(M)$ space. Then compute equation \eqref{eq:29.6}. Computing integer logarithm takes $\BigO(\ln M)$ for each $2 \le a \le M$. Then there are $\lfloor \log_2 M \rfloor$ calculations of $D(\cdot)$, each taking $\BigO(M (\ln M)^2)$ time and $\BigO(M \ln M)$ space. 

Time complexity: $\BigO(M (\ln M)^3)$.

Space complexity: $\BigO(M \ln M)$.

\answer

9183

\end{document}
